from typing import List
from collections import deque, defaultdict
import heapq


class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adjs = defaultdict(list)
        for u, v, dist in flights:
            adjs[u].append([v, dist])

        distance = defaultdict(dict)
        distance[src][0] = 0

        q = [(0, src, 0)]
        while q:
            du, u, hu = heapq.heappop(q)  # hu: hop of u
            if du > distance[u][hu]:
                continue
            # print('pop', u, hu, du)
            for v, dist in adjs[u]:
                hv = hu + 1
                if hv > k + 1:
                    continue
                dv = distance[u][hu] + dist
                max_hop = -1
                if v in distance:
                    for x in distance[v]:
                        if x <= hv:
                            max_hop = max(max_hop, x)
                if max_hop == -1 or (dv < distance[v][max_hop]):
                    distance[v][hv] = dv
                    heapq.heappush(q, (dv, v, hv))

        inf = 10 ** 10
        res = inf

        for hop, dist in distance[dst].items():
            res = min(res, dist)
        if res == inf:
            res = -1
        return res


class BrutalSolution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:
        adjs = defaultdict(list)
        for u, v, dist in flights:
            adjs[u].append([v, dist])

        result = []
        path = []
        def backtrace(u, du):
            if u in path:
                return
            path.append(u)
            if u == dst:
                result.append([len(path) - 1, du])
            for v, dist in adjs[u]:
                backtrace(v, du + dist)
            path.pop()
        backtrace(src, 0)

        result = [x for x in result if x[0] <= k + 1]
        if len(result) == 0:
            return -1
        return min(result, key=lambda x: x[1])[1]

solution = Solution()
brutal_solution = BrutalSolution()


def random_test():
    import random
    from algorithm import random_directed_graph
    random.seed(0)
    def test():
        n = random.randint(2, 7)
        src, dst = random.sample(range(n), k=2)
        k = random.randint(0, n-1)
        edges = random_directed_graph(n_nodes=n)
        costs = random.choices(range(1, 10), k=len(edges))
        flights = [[u, v, c] for (u, v), c in zip(edges, costs)]
        args = (n, flights, src, dst, k)
        res1 = Solution().findCheapestPrice(*args)
        res2 = brutal_solution.findCheapestPrice(*args)
        if res1 != res2:
            print(args, res1, res2)
    for i in range(100000):
        test()
random_test()


